The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Group communication is nowadays a well established topic in distributed computing. It emerged over the years as a topic with a strong synergy between theory and practice: group communication is highly relevant for building distributed systems, and is also of theoretical importance, because of the difficult problems it addresses. The paper presents an - inevitably subjective - retrospective of the...
This article is based on the remarks Iwas invited to make at the 2002Workshop on Future Directions in Distributed Computing on the impact of academic distributed systems research on the real world. In this short piece I document the gist of the presentation.
The Consensus problem lies at the heart of many distributed computing problems one has to solve when designing reliable applications on top of unreliable distributed asynchronous systems. There is a large literature where theoretical and practical aspects of this problem are studied1, that can be informally stated in terms of three requirements. Each process proposes a value, and has to decide on...
Consensus is usually expressed in terms of agreement among a set of processes. Instead, we characterize it in terms of three classes of agents: Proposers A proposer can propose values. Acceptors The acceptors cooperate in some way to choose a single proposed value. Learners A learner can learn what value has been chosen.
Most fault-tolerant algorithms are designed assuming that out of n components, no more than t can be faulty. For example, solutions to the Consensus problem are usually developed assuming no more than t of the n processes are faulty, where “being faulty” is specialized by a failure model. We call this the t of n assumption (also known as threshold model). It is a convenient assumption to make. For...
Reaching agreement in a distributed system is a fundamental issue of both theoretical and practical importance. Consensus and non-blocking atomic commitment are two wellknown versions of this paradigm. The Consensus problem considers a fixed collection of processors each of which has an initial value drawn from some domain V , and processors must eventually decide on the same value1; moreover, the...
We consider the consensus problem in a message-passing system where processes can crash: Each process has an input, and each correct process must decide on an output, such that all correct processes decide on the same output, and this output is the input of one of the processes. Consensus is an important building block for fault-tolerant systems. It is well-known that consensus is not solvable in...
Theoretical evaluation of performance, availability, and reliability of distributed algorithms is always based on models and metrics that make some simplifying assumptions. Such assumptions are needed in order to have simple abstractions for reasoning about algorithms. However, such assumptions often lead to models, metrics, and analyses that fail to capture important aspects of actual system behavior...
Optimism is a well-known technique to enhance the performance of distributed protocols. Optimistic approaches exploit properties exhibited by the system with certain likelihood, (i.e., that certain kinds of scenarios will prevail over others) to outperform the corresponding conservative protocol. These properties are usually referred as optimistic assumptions (e.g., an optimistic assumption is that...
As the world becomes increasingly interconnected, more and more important services such as business transactions are deployed as access-anywhere services - services that are accessible by remote devices through the Internet and mobile networks. Such services often must access confidential data to provide service. For example, an online bank service must access a user’s checking account to process...
Security considerations play an increasingly important role for distributed computing. In the future, dependable distributed systems for open networks can no longer be designed without taking malicious attacks into account. The enabling technology for security is cryptography, which has been placed on sound theoretical foundations during the last twenty years. The formal model of modern cryptography...
This research direction aims to develop and analyze algorithms to solve problems of communication and data sharing in highly dynamic distributed environments. The term dynamic here encompasses many types of changes, including changing network topology, processor mobility, changing sets of participating client processes, a wide range of types of processor and network failures, and timing variations...
Beginning with the earliest assembly languages, programming even simple centralised and sequential applications was very cumbersome. Major advances in computing came with the adoption of programming languages that promoted the use of machine independent data abstractions like sets, arrays, and records, as well as control abstractions like while, ifand repeat. With the arrival of parallel machines...
Distributed applications are characterized by the fact that the processes they are made up of execute on possibly geographically dispersed nodes. An important problem the underlying distributed system has to solve lies in maintaining the consistency of the state that is shared by such processes. Unfortunately, the non-instantaneity of message transmissions and failure occurrences make this fundamental...
The Internet is seeing a rapid increase in on-line newspapers and advertising for new products and sales.Yet only primitive mechanisms are available to help users discover and obtain that subset of these news items likely to be of interest. Current search engines are really only first step. For locating news providers, word-of-mouth and mass mailings are still used; for retrieval of news items, users...
In this paper, we define aggregation as the ability to summarize information. In the area of sensor networks [16.2] it is also referred to as data fusion. It is the basis for scalability for many, if not all, large networking services. For example, address aggregation allows Internet routing to scale.Without it, routing tables would need a separate entry for each Internet address. Besides a problem...
This paper surveys exisiting work in distributed lookup services using dynamic shared hash tables (DHTs), with the goal of pointing out open issues and key challenges. Discovering and locating resources in networked systems are quintessential problems of distributed computing. Their goal is to design a distributed lookup service that allows clients to contact the service from anywhere and find any...
The focus of this position paper is on the most appropriate form of middleware to offer in support of distributed system management, control, information sharing and multicast communication. Our premise is that technology has been deficient in all of these areas. If recent advances can be transitioned into general practice, this could enable a new generation of better distributed systems, with value...
Structured peer-to-peer (p2p) overlay networks like CAN, Chord, Pastry and Tapestry [19.14], [19.20], [19.17], [19.22] provide a self-organizing substrate for large-scale p2p applications. They can implement a scalable, fault-tolerant distributed hash table (DHT), in which any item can be located within a small number of routing hops using a small per-node routing table. These systems have been used...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.